// https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/

// 题干：给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。
//       同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
//      每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。
//      你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
//      请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

// 示例：输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
//      输出：1

// 碎语：BFS解决图论边权相同的模板题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int m, n;
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& e)
    {
        // 怎么抽象成图论，本题边权为1
        m = maze.size(), n = maze[0].size();
        bool vis[m][n];
        memset(vis, 0, sizeof(vis));

        queue<pair<int, int>> q;
        q.push({e[0], e[1]});
        vis[e[0]][e[1]] = true;

        int step = 0;
        while (q.size()){
            step++;
            int sz = q.size();

            for (int i = 0 ; i < sz ; i++){
                auto& [a, b] = q.front();
                q.pop();

                for (int j = 0 ; j < 4 ; j++){
                    int x = a + dx[j], y = b + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.'){
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }

        return -1;
    }
};


// 示例：输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
int main()
{
    Solution sol;
    vector<vector<char>> maze = {
            {'+','+','.','+'},
            {'.','.','.','+'},
            {'+','+','+','.'}
    };
    vector<int> entrance = {1,2};

    cout << sol.nearestExit(maze, entrance) << endl;

    return 0;
}